package com.liuwei.spring.cloud.junit.leetcode.dp;

import lombok.extern.slf4j.Slf4j;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

@Slf4j
public class RainWater {
    /**
     * 接雨水: https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
     */
    public static void main(String[] args) {
        RainWater solution = new RainWater();
        int[] height = new int[]{4,2,0,3,2,5};
        int result = solution.trap(height);
        log.info("result:{}",result);
    }

    public int trap(int[] height) {
        int count = 0;
        for(int i=0;i<height.length;i++) {
            int leftMax = findMaxValue(height, 0, i - 1,true);
            int rightMax = findMaxValue(height, i + 1, height.length - 1,false);
            int water = 0;
            if (leftMax <= height[i] || rightMax <= height[i]) {
                // 无法存水
            }else{
                water = Math.min(leftMax,rightMax) - height[i];
                count = count + water;
            }
            log.info("current:{} left:{} right:{} water:{}",height[i],leftMax,rightMax,water);
        }
        return count;
    }

    private int findMaxValue(int[] source,int startIndex,int endIndex){
        if(startIndex<=0){
            startIndex = 0;
        }
        if(startIndex>=source.length-1){
            startIndex = source.length-1;
        }
        int max = 0 ;
        if(source!=null && source.length>0){
            for (int i = startIndex; i <= endIndex; i++) {
                if(source[i]>max){
                    max = source[i];
                }
            }
        }
        return max;
    }

    public static Map<String,Integer> MAX_VALUE = new ConcurrentHashMap<>();
    private int findMaxValue(int[] source,int startIndex,int endIndex,boolean indexStartFromZero){
        int max = 0 ;
        if(startIndex<=0){
            startIndex = 0;
        }
        if(endIndex<=0){
            endIndex = 0;
        }
        if(startIndex>=source.length-1){
            startIndex = source.length-1;
        }
        if(endIndex>=source.length-1){
            endIndex = source.length-1;
        }
        String key = startIndex+"-"+endIndex;
        if(startIndex == endIndex){
            max = source[startIndex];
            return max;
        }
        if(MAX_VALUE.containsKey(key)){
            return MAX_VALUE.get(key);
        }else{
            int current;
            int history;
            if(indexStartFromZero){
                current = source[endIndex];
                history = findMaxValue(source, startIndex, endIndex-1, indexStartFromZero);
            }else{
                current = source[startIndex];
                history = findMaxValue(source, startIndex+1, endIndex, indexStartFromZero);
            }
            max = current>=history?current:history;
            MAX_VALUE.put(key,max);
            return max;
        }
    }
}
